/**
 * @param {string} s
 * @return {number}
 */
 var longestPalindromeSubseq = function(s) {
    // dp[i][j] 表示以在区间i,j范围内最长子序列的长度
    let dp = new Array(s.length).fill(0).map(()=>new Array(s.length).fill(0))
    // 初始化 当i和j相同的时候 dp[i][j]是1  因为有一个元素 那么他的最长回文子序列长度就是1
    for(let i = 0;i < s.length;i++){
      dp[i][i] = 1
    }
    for(let i = s.length - 1;i >= 0;i--){
      // 从后向前遍历 当i>=0 的时候一直遍历
      for(let j = i+1;j < s.length;j++){
        // 从i+1遍历 一直到长度结尾
        if(s[i] === s[j]){
          // 如果i位置的和j位置的相同 那么以i,j为结尾的最长子序列的长度就是以i+1,j-1位结尾的最长子序列的长度+1
          dp[i][j] = dp[i+1][j-1] + 2
        }else{
          // 如果两者不相同 那么就是以i+1,j 为结尾的最长子序列的长度 和以i,j-1位结尾的最长子序列的长度的最大值
          dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1])
        }
      }
    }
    // 最后返回从起始到最后他的最长子序列的长度
    return dp[0][s.length-1]
};